package leetcode.code600;

public class Solution3 extends Solution600 {

	private final char ZERO = '0';
	private final char ONE = '1';

	@Override
	public int findIntegers(int n) {
		String str = Integer.toBinaryString(n);
		char[] max = str.toCharArray();
		char[] chars = new char[str.length()];
		int[][][] cache = new int[str.length() + 1][str.length() + 1][2];
		for (int i = 0; i < str.length() + 1; i++) {
			for (int j = 0; j < str.length() + 1; j++) {
				cache[i][j][0] = -1;
				cache[i][j][1] = -1;
			}
		}
		int ans = this.findIntegers(0, -1, chars, max, 1, cache);
		return ans;
	}

	private int findIntegers(int index, int lastIndex, char[] chars, char[] max, int lastMatchMax, int[][][] cache) {
//		System.out.println(index + " " + lastIndex + " " + lastMatchMax);
		if (index == chars.length) {
			cache[index][lastIndex][lastMatchMax] = 1;
			return 1;
		}
		if (lastIndex != -1 && cache[index][lastIndex][lastMatchMax] != -1)
			return cache[index][lastIndex][lastMatchMax];
		int ans = 0;
		chars[index] = ZERO;
		int indexMatch = lastMatchMax == 1 ? chars[index] == max[index] ? 1 : 0 : 0;
		ans += findIntegers(index + 1, index, chars, max, indexMatch, cache);
		if (lastIndex == -1 || (lastMatchMax == 0 && chars[lastIndex] == ZERO)
				|| (lastMatchMax == 1 && chars[lastIndex] == ZERO && max[index] == ONE)) {
			chars[index] = ONE;
			indexMatch = lastMatchMax == 1 ? chars[index] == max[index] ? 1 : 0 : 0;
			ans += findIntegers(index + 1, index, chars, max, indexMatch, cache);
		}
		if (lastIndex != -1)
			cache[index][lastIndex][lastMatchMax] = ans;
		return ans;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
//		so.debug1();
//		so.debug2();
//		so.debug3();

//		for (int i = 0; i < 101; i++) {
		int i = 100;
		int r = so.findIntegers(i);
		System.out.println(i + " " + r);
//		}

	}

}
